/*
 * @lc app=leetcode.cn id=241 lang=cpp
 *
 * [241] 为运算表达式设计优先级
 *
 * https://leetcode.cn/problems/different-ways-to-add-parentheses/description/
 *
 * algorithms
 * Medium (73.62%)
 * Likes:    564
 * Dislikes: 0
 * Total Accepted:    43.3K
 * Total Submissions: 58.8K
 * Testcase Example:  '"2-1-1"'
 *
 * 给你一个由数字和运算符组成的字符串 expression ，按不同优先级组合数字和运算符，计算并返回所有可能组合的结果。你可以 按任意顺序
 * 返回答案。
 *
 *
 *
 * 示例 1：
 *
 *
 * 输入：expression = "2-1-1"
 * 输出：[0,2]
 * 解释：
 * ((2-1)-1) = 0
 * (2-(1-1)) = 2
 *
 *
 * 示例 2：
 *
 *
 * 输入：expression = "2*3-4*5"
 * 输出：[-34,-14,-10,-10,10]
 * 解释：
 * (2*(3-(4*5))) = -34
 * ((2*3)-(4*5)) = -14
 * ((2*(3-4))*5) = -10
 * (2*((3-4)*5)) = -10
 * (((2*3)-4)*5) = 10
 *
 *
 *
 *
 * 提示：
 *
 *
 * 1 <= expression.length <= 20
 * expression 由数字和算符 '+'、'-' 和 '*' 组成。
 * 输入表达式中的所有整数值在范围 [0, 99] 
 *
 *
 */

// @lc code=start
#include <iostream>
#include <sstream>
#include <vector>
using namespace std;
class Solution {
public:
    vector<int> diffWaysToCompute(string expression) {
        // 分治
        /* vector<int> ways;
        for (int i = 0; i < (int)expression.length(); ++i) {
            char c = expression[i];
            if (c == '+' || c == '-' || c == '*') {
                vector<int> left = diffWaysToCompute(expression.substr(0, i));
                vector<int> right = diffWaysToCompute(expression.substr(i + 1));
                for (const int &l : left) {
                    for (const int &r : right) {
                        switch (c) {
                        case '+':
                            ways.push_back(l + r);
                            break;
                        case '-':
                            ways.push_back(l - r);
                            break;
                        case '*':
                            ways.push_back(l * r);
                            break;
                        }
                    }
                }
            }
        }
        if (ways.empty())
            ways.push_back(stoi(expression));
        return ways; */

        // DP
        vector<int> data;
        vector<char> ops;
        int num = 0;
        char op = ' ';
        istringstream ss(expression + "+");
        while (ss >> num && ss >> op) {
            data.push_back(num);
            ops.push_back(op);
        }
        int n = data.size();
        vector<vector<vector<int>>> dp(n, vector<vector<int>>(n, vector<int>()));
        for (int i = 0; i < n; ++i) {
            for (int j = i; j >= 0; --j) {
                if (i == j) {
                    dp[j][i].push_back(data[i]);
                }
                else {
                    for (int k = j; k < i; k += 1) {
                        for (auto left : dp[j][k]) {
                            for (auto right : dp[k + 1][i]) {
                                int val = 0;
                                switch (ops[k]) {
                                case '+':
                                    val = left + right;
                                    break;
                                case '-':
                                    val = left - right;
                                    break;
                                case '*':
                                    val = left * right;
                                    break;
                                }
                                dp[j][i].push_back(val);
                            }
                        }
                    }
                }
            }
        }
        return dp[0][n - 1];
    }
};
// @lc code=end
